# 集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
#  第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
#  工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
#  有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
#
#  示例 1：
# 输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
# 输出：2
# 解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
# 总的来说，有两种计划。
#
#  示例 2：
# 输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
# 输出：7
# 解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
# 有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。
from typing import List


class Solution:
    def profitableSchemes2(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        """
        动态规划
        数组的元素只能选或者不选，不可重复选取
        两重背包，不仅要考虑使用的人数不能超过最大，同时得考虑使用的人数能产生最少的利润
        :param n:
        :param minProfit:
        :param group:
        :param profit:
        :return:
        """
        size, res = len(group), 0
        # dp[i][j][k] = m 表示在前 i 个工作中(group[0:i + 1)，使用j个人，最少能产生 k 的利润的组合数为 m
        # 三维数组三种写法如下
        # dp = [[[0] * (minProfit + 1)] * (n + 1)] * (size + 1)  # shape(3, 6, 4) (浅拷贝不可取)
        # dp = [[[0] * (minProfit + 1) for __ in range(n + 1)] for _ in range(size + 1)]  # shape(3, 6, 4), 部分浅拷贝
        dp = [[[0 for k in range(minProfit + 1)] for j in range(n + 1)] for i in
              range(size + 1)]  # shape(3, 6, 4), 全部深拷贝
        dp[0][0][0] = 1
        for i in range(1, size + 1):
            for j in range(n + 1):
                for k in range(minProfit + 1):
                    if j >= group[i - 1]:
                        dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])]
                    else:
                        dp[i][j][k] = dp[i - 1][j][k]

        for j in range(n + 1):  # 遍历能通过 <= n 个人完成工作的组合数，得到结果
            res += dp[size][j][minProfit]
        return res % (10 ** 9 + 7)

    def profitableSchemes1(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        """
        解法一(超时)：
        对于每个工作有选择做该工作和不做两种可能
        尝试每个工作做或者不做的组合然后判断该组合是否可以达到目标的最小值
        :param n:
        :param minProfit:
        :param group:
        :param profit:
        :return:
        """
        size, res = len(group), 0 if minProfit > 0 else 1

        def dfs(index: int, curTotalProfit: int, curTotalWorkedPeople: int) -> None:
            if index == size or curTotalWorkedPeople < 0:
                return
            if curTotalProfit + profit[index] >= minProfit and curTotalWorkedPeople - group[index] >= 0:
                nonlocal res
                res += 1
            dfs(index + 1, curTotalProfit + profit[index], curTotalWorkedPeople - group[index])  # 做当前工作
            dfs(index + 1, curTotalProfit, curTotalWorkedPeople)  # 不做当前工作

        dfs(0, 0, n)
        return res % (10 ** 9 + 7)

    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        return self.profitableSchemes2(n, minProfit, group, profit)


if __name__ == "__main__":
    n, minProfit, group, profit = 5, 3, [2, 2], [2, 3]
    # n, minProfit, group, profit = 10, 5, [2, 3, 5], [6, 7, 8]
    # n, minProfit, group, profit = 64, 0, [80, 40], [88, 88]
    n, minProfit, group, profit = 95, 53, \
                                  [82, 7, 18, 34, 1, 3, 83, 56, 50, 34, 39, 38, 76, 92, 71, 2, 6, 74, 1, 82, 22,
                                   73, 88, 98, 6, 71, 6, 26, 100, 75, 57, 88, 43, 16, 22, 89, 7, 9, 78, 97, 22,
                                   87, 34, 81, 74, 56, 49, 94, 87, 71, 59, 6, 20, 66, 64, 37, 2, 42, 30, 87, 73,
                                   16, 39, 87, 28, 9, 95, 78, 43, 59, 87, 78, 2, 93, 7, 22, 21, 59, 68, 67, 65,
                                   63, 78, 20, 82, 35, 86], \
                                  [45, 57, 38, 64, 52, 92, 31, 57, 31, 52, 3, 12, 93,8, 11, 60, 55, 92, 42, 27, 40,
                                   10, 77, 53, 8, 34, 87, 39, 8, 35, 28, 70, 32, 97, 88, 54, 82, 54, 54, 10, 78, 23,
                                   82, 52, 10, 49, 8, 36, 9, 52, 81, 26, 5, 2, 30, 39, 89, 62, 39, 100, 67, 33, 86,
                                   22, 49, 15, 94, 59, 47, 41, 45, 17, 99, 87, 77, 48, 22, 77, 82, 85, 97, 66, 3, 38,
                                   49, 60, 66]
    print(Solution().profitableSchemes(n, minProfit, group, profit))
